package com.zjsru.oneDay;

import java.util.Arrays;

/**
 * 学生分数的最小差值
 * <p>
 * 输入：nums = [9,4,1,7], k = 2
 * 输出：2
 * 解释：选出 2 名学生的分数，有 6 种方法：
 * - [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
 * - [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
 * - [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
 * - [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
 * - [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
 * - [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
 * 可能的最小差值是 2
 */
public class minimumDifference {
    public int minimumDifference(int[] nums, int k) {
        //暴力,缺点 多次无用计算
//        Arrays.sort(nums);
        int n = nums.length;
        int ans = nums[k - 1] - nums[0];
        if (n == 1) return 0;
        for (int i = 0; i < n; i++) {
            for (int j = k - 1 + i; j < n; j++) {
                int res = nums[j] - nums[i];
                ans = Math.min(res, ans);
            }
        }
        return ans;
    }

    //题解 滑动窗口＋排序
//    public int minimumDifference(int[] nums, int k) {
//       Arrays.sort(nums);
//       int n = nums.length , ans = nums[k - 1] -nums[0];
//        for (int i = k; i < n; i++) {
//            ans  = Math.min(ans, nums[i] - nums[i - k + 1]);
//        }
//        return ans;
//    }

    public static void main(String[] args) {
        minimumDifference minimumDifference = new minimumDifference();
        int[] nums = new int[]{9, 4, 1, 7};
        int k = 2;
        System.out.println(minimumDifference.minimumDifference(nums, k));
    }
}
